package 链表;

import java.security.SecureRandom;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * @author yzh
 * @version 1.0
 * @date 2022/5/8 19:42
 */
public class SkipListInt {
    private static final double UP_RATE = 0.5;
    private Node head;
    private final Deque<Node> stack = new ArrayDeque<>();
    private final SecureRandom random = new SecureRandom();

    public static class Node {
        public int val;
        public Node down, right;

        public Node(int _val) {
            val = _val;
        }
    }

    public SkipListInt() {
        head = new Node(-1);
    }

    public Node findPredecessor(int val) {
        stack.clear();
        for (Node cur = head, r = cur.right; ; ) {
            if (r != null) {
                if (r.val < val) {
                    cur = r;
                    r = cur.right;
                    continue;
                }
            }
            if (cur.down == null) return cur;
            stack.push(cur);
            cur = cur.down;
            r = cur.right;
        }
    }

    public Node search(int val) {
        Node pre = findPredecessor(val);
        if (pre.right == null) return null;
        if (pre.right.val == val) return pre.right;
        return null;
    }

    public void addAll(List<Integer> list) {
        for (Integer num : list) add(num);
    }

    public void add(int val) {
        Node predecessor = findPredecessor(val);
        if (predecessor.right != null && predecessor.right.val == val) return;
        Node node = new Node(val);
        node.right = predecessor.right;
        predecessor.right = node;
        Node up, down;
        for (; ; ) {
            if (random.nextDouble() < UP_RATE) break;
            down = node;
            node = new Node(val);
            node.down = down;
            if (stack.isEmpty()) {
                Node newHead = new Node(-1);
                newHead.down = head;
                newHead.right = node;
                head = newHead;
                break;
            }
            up = stack.pop();
            node.right = up.right;
            up.right = node;
        }
    }

    public void del(int val) {
        Node predecessor = findPredecessor(val);
        if (predecessor.right == null || predecessor.right.val != val) return;
        for (; ; ) {
            if (predecessor.right == null || predecessor.right.val != val) break;
            predecessor.right = predecessor.right.right;
            if (head.right == null && head.down != null) {
                Node tmp = head;
                head = head.down;
                tmp.down = null;
            }
            if (stack.isEmpty()) break;
            predecessor = stack.pop();
        }
    }

    public void ergodic() {
        for (Node down = head; down != null; down = down.down) {
            Node cur = down;
            while (cur.right != null) {
                System.out.print(cur.right.val + " ");
                cur = cur.right;
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SkipListInt skipList = new SkipListInt();
        skipList.addAll(Arrays.asList(2, 10, 3, 4, 1, 0, 99));
        skipList.ergodic();
        System.out.println(skipList.search(3).val);
    }

}
